package dfs;

import java.util.Arrays;

public class leetcode60排列序列 {
    public String getPermutation(int n, int k) {
        char[] str = new char[n];
        for (int i = 0; i < n; i++) {
            str[i] = (char)(i + 1 + '0');
        }
        for (int i = 0; i < n; i++) {
            int index = 0;
            int mod = mod(n - i - 1);
            while (k > mod) {
                k -= mod;
                index++;
            }
            swap(str, i, i + index);
            if (i < n - 1) {
                Arrays.sort(str, i + 1, n);
            }
            if (k == 1) {
                break;
            }
        }
        return new String(str);
    }

    public int mod(int n) {
        if (n == 0) {
            return 1;
        } else {
            return n * mod(n - 1);
        }
    }

    public void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
}
